93. 复原 IP 地址

Similar Question

Solution Tips

方案一: 回溯 + N 叉树切割思路

var restoreIpAddresses = function (s) {
    // 感觉和 131 相似度极高, 这次采用 for 思路理解一下
    // for 思路就是通过 for 循环 index 来判断下一个切割, 到底在哪里 
    const res = [];
    dfs([], 0);
    return res;

    function dfs(path, index) {
        if (index === s.length) {
            res.push(path.join('.'))
            return;
        }

        // 只能切割3次
        if (path.length >= 4) {
            return;
        }

        // 剩余的切割平均值大于3也可以剪枝
        const restPartition = 4 - path.length;
        if ((s.length - index) / restPartition > 3) {
            return;
        }

        for (let i = index + 1; i <= s.length && i - index <= 3; i++) {
            const sub = s.slice(index, i);

            if (isValidAddress(sub)) {
                path.push(sub);
                // 因为 slice api 的缘故, 从 i 开始继续寻找下一次切割的位置
                dfs(path, i);
                path.pop();
            }
            // 不 push 的情况, 就 continue 就可以了
        }

    }

    function isValidAddress(s) {
        let n = s.length;
        if (s === '0') return true;
        if (s.startsWith('0')) return false;
        const int = parseInt(s);
        if (int > 255) return false;
        return true;
    }
};
console.log(restoreIpAddresses("25525511135"));

特别地，由于 IP 地址的每一段不能有前导零，因此如果 s[segStart] 等于字符 0，那么 IP 地址的第 segId 段只能为 0，需要作为特殊情况进行考虑

可以加上这一种特殊的剪枝